package com.bbz.core.Youku;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 提供方法，直接调用，支持任意个数组的合并成一个数组，并且完成排序，每个数组元素个数不定。
 * 需要提供两个方法，分别做到时间复杂度最低、空间复杂度最低。并说明两个方法的时间复杂度和空间复杂度
 */
public class Test_2 {
    public static void main(String args[]) {
        //数据准备
        Integer[] ints_1 = new Integer[]{1, 2, 3};
        Integer[] ints_2 = new Integer[]{23, 43, 123};
        Integer[] ints_3 = new Integer[]{30, 198, 45};
        ArrayList<Integer[]> arrayLis = new ArrayList<>();
        arrayLis.add(ints_1);
        arrayLis.add(ints_2);
        arrayLis.add(ints_3);
        merge(arrayLis);
    }

    public static void merge(List<Integer[]> lists) {
        List<Integer> tempList = new ArrayList();
        //合并
        for (int i = 0; i < lists.size(); i++) {
            tempList.addAll(Arrays.asList(lists.get(i)));
        }
        //排序
        System.out.println(tempList);
        sort(tempList);
        System.out.println(tempList);
    }

    //二分法插入排序（按二分法找到合适位置插入）时间复杂度是O(logn)
    public static void sort(List<Integer> a) {
        for (int i = 0; i < a.size(); i++) {
            int temp = a.get(i);
            int left = 0;
            int right = i - 1;
            int mid = 0;
            while (left <= right) {
                mid = (left + right) / 2;
                if (temp < a.get(mid)) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            for (int j = i - 1; j >= left; j--) {
                a.set(j + 1, a.get(j));
            }
            if (left != i) {
                a.set(left, temp);
            }
        }
    }
}
